package com.rn.gypsophila.dsalg.eliminate;

import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Description: 基于 HashMap 和 双向链表实现 LRUCache
 * <p>
 * 1.设计原则：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。
 * 2.设计思路：可以使用 HashMap 存储 k，这样可以做到 set 和 get k的时间都是 O(1)，而 HashMap 的 value 指向双向链表实现的 LRUCache 的 Node 节点
 * 3.核心步骤：
 * - set(k, v)，首先在 HashMap 找到 key 对应的节点，如果节点存在，更新节点的值，并把这个节点移到队头；如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 key。
 * - get(k)，通过 HashMap 找到 LRUCache 链表节点，因为根据LRU 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。
 * 4.时间复杂度：O(1)
 *
 * @author 然诺
 * @date 2021/04/07
 */
public class LRUCache<K, V> implements Iterable<K> {
    private Map<K, Node> cache;
    private int maxSize;
    private Node head, tail;

    private class Node {
        K k;
        V v;
        Node pre;
        Node next;
    }

    public LRUCache(int maxSize) {
        this.maxSize = maxSize;
        this.cache = new ConcurrentHashMap<>(maxSize * 4 / 3);

        head = new Node();
        head.pre = null;

        tail = new Node();
        tail.next = null;

        head.next = tail;
        tail.pre = head;
    }

    public V get(K k) {
        Node node = cache.get(k);
        if (node == null) {
            return null;
        }
        // 将访问的节点移到头部
        this.moveToHead(node);
        return node.v;
    }

    public void set(K k, V v) {
        Node node = cache.get(k);
        if (node == null) {
            node = new Node();
            node.k = k;
            node.v = v;

            this.cache.put(k, node);
            this.appendHead(node);

            if (cache.size() > maxSize) {
                Node tail = this.removeTail();
                this.cache.remove(tail.k);
            }
        } else {
            node.v = v;
            this.moveToHead(node);
        }
    }

    /**
     * 始终在头之后添加新节点
     */
    private void appendHead(Node node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    /**
     * 移除节点
     */
    private void removeNode(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
        node.pre = null;
        node.next = null;
    }

    /**
     * 移动节点到头部
     */
    private void moveToHead(Node node) {
        this.removeNode(node);
        this.appendHead(node);
    }

    /**
     * 移除尾部节点
     */
    private Node removeTail() {
        Node res = tail.pre;
        this.removeNode(res);
        return res;
    }

    @Override
    public Iterator<K> iterator() {
        return new Iterator<K>() {
            private Node cur = head.next;

            @Override
            public boolean hasNext() {
                return cur != tail;
            }

            @Override
            public K next() {
                Node node = cur;
                cur = cur.next;
                return node.k;
            }
        };
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> lruCache = new LRUCache<>(3);
        lruCache.set("k_1", 1);
        lruCache.set("k_2", 2);
        lruCache.set("k_3", 3);
        lruCache.set("k_4", 4);
        System.out.println(lruCache.head.next.k);
        System.out.println(lruCache.get("k_2"));
        System.out.println(lruCache.head.next.k);
    }
}
